#include <iostream>
#include <algorithm>
#include "TestSortHelper.h"
#include "MergeSort.h"
#include "InsertSort.h"

using namespace std;

static long swaptimes_p2_stack_err = 0;
static long swaptimes_p2 = 0;
//对 arr分割 [l,r]排序
template <typename T>
int* __partition3(T arr[], int l, int r) {
    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    int lt = l;
    int gt = r+1;
    int i = l + 1;

    while (i < gt) {
        if (arr[i] > v) {
            swap(arr[gt - 1], arr[i]);
            gt--;
        }
        else if (arr[i] < v) {
            swap(arr[lt + 1], arr[i]);
            lt++;
            i++;
        }
        else {
            i++;
        }
    }
    swap(arr[l], arr[lt]);
    static int n[2];
    n[0] = lt - 1;
    n[1] = gt;
    return n;
}


template <typename T>
int __partition2(T arr[], int l, int r){

    swap( arr[l] , arr[rand()%(r-l+1)+l] );
    T v = arr[l];

    // arr[l+1...i) <= v; arr(j...r] >= v
    int i = l+1, j = r;
    while( true ){
        while( i <= r && arr[i] < v )
            i ++;

        while( j >= l+1 && arr[j] > v )
            j --;

        if( i > j )
            break;

        swap( arr[i] , arr[j] );
        swaptimes_p2++;
        i ++;
        j --;
    }

    swap( arr[l] , arr[j]);
    cout<<j << " ";
    return j;
}

//对 arr分割 [l,r]排序
template <typename T>
int __partition2__stack_err(T arr[], int l, int r) {
//    cout<<l<<"--"<<r<<endl;
    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    int i = l+1;
    int j = r;
    while (true) {
        while (i<=r && arr[i] <= v) i++; // 这里使用<= 在重复数据很多的时候，会导致j的偏移很大，分的不均匀。导致性能下降
        while (j>=l+1 && arr[j] >= v) j--;
        if (j <= i){
//            cout<<i<<":"<<j<<endl;
            break;
        }
        swap(arr[i], arr[j]);
        swaptimes_p2_stack_err++;
        i++;
        j--;
    }
    swap(arr[l], arr[j]);
    cout<<j << " ";
    return j;

}

//对 arr分割 [l,r]排序
template <typename T>
int __partition1(T arr[], int l, int r) {
    swap(arr[l],arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    int j = l;
    for (int i = l + 1;i <= r;i++) {
        if (arr[i] < v) {
            swap(arr[++j], arr[i]);
        }
    }
    swap(arr[l], arr[j]);
    return j;

}

//对 arr分割 [l,r]排序
template <typename T>
int __partition(T arr[], int l, int r) {
    T v = arr[l];

    int j = l;
    for (int i = l + 1;i <= r;i++) {
        if (arr[i] < v) {
            swap(arr[++j], arr[i]);
        }
    }
    swap(arr[l], arr[j]);
    return j;

}


//对 __quickSort [l,r]排序
template <typename T>
void __quickSort(T arr[], int l, int r) {
//    if (r <= l) {
//        return;
//    }

    if (r - l <= 15) {
        insertSort(arr, l, r);
        return;
    }

//    int* j = __partition3(arr, l, r);
//    __quickSort(arr, l, j[0]);
//    __quickSort(arr, j[1], r);
//    delete j;

    int j = __partition(arr, l, r);
//    int j = __partition2(arr, l, r);
//    int j = __partition(arr, l, r);
//    int j = __partition_srand(arr, l, r);
    __quickSort(arr, l, j);
    __quickSort(arr, j+1, r);

}

//对 __quickSort [l,r]排序
template <typename T>
void __quickSort1(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertSort(arr, l, r);
        return;
    }
    int j = __partition1(arr, l, r);
    __quickSort1(arr, l, j);
    __quickSort1(arr, j+1, r);

}
//对 __quickSort [l,r]排序
template <typename T>
void __quickSort2(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertSort(arr, l, r);
        return;
    }
    int j = __partition2(arr, l, r);
    __quickSort2(arr, l, j);
    __quickSort2(arr, j+1, r);

}

template <typename T>
void __quickSort2_stack_err(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertSort(arr, l, r);
        return;
    }
    int j = __partition2__stack_err(arr, l, r);
    __quickSort2_stack_err(arr, l, j);
    __quickSort2_stack_err(arr, j+1, r);

}
//对 __quickSort [l,r]排序
template <typename T>
void __quickSort3(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertSort(arr, l, r);
        return;
    }
    int *j = __partition3(arr, l, r);
    __quickSort3(arr, l, j[0]);
    __quickSort3(arr, j[1], r);
    delete[] j;

}


template <typename T>
void quickSort(T arr[], int n) {
    srand(time(NULL));
    __quickSort(arr, 0, n - 1);
}

template <typename T>
void quickSort1(T arr[], int n) {
    srand(time(NULL));
    __quickSort1(arr, 0, n - 1);
}

template <typename T>
void quickSort2(T arr[], int n) {
    srand(time(NULL));
    __quickSort2(arr, 0, n - 1);
}

template <typename T>
void quickSort2_stack_err(T arr[], int n) {
    srand(time(NULL));
    __quickSort2_stack_err(arr, 0, n - 1);
}

template <typename T>
void quickSort3(T arr[], int n) {
    srand(time(NULL));
    __quickSort3(arr, 0, n - 1);
}

int main() {
//    int n = 1000000;
//    cout << "Test for Random Array, size = " << n << ", randome range [0, " << n << "]" << endl;
//    int *arr1 = TestSortHelper::generateRandomArray(n, 0, n);
//    int *arr2 = TestSortHelper::copyIntArray(arr1, n);
//    TestSortHelper::printArray(arr1,n);
//
//    TestSortHelper::testSort("merge up-bottom Sort Sort", mergeSortUB, arr1, n);
//    TestSortHelper::printArray(arr1, n);
//    TestSortHelper::testSort("quick Sort", quickSort, arr2, n);
//    TestSortHelper::printArray(arr2, n);
//
//    delete[] arr1;
//    delete[] arr2;

    int n = 100;
    int sw = 3;
    cout << "Test for Random Array, size = " << n << ", randome range [0, " << sw << "]" << endl;
    int *arr1 = TestSortHelper::generateRandomArray(n, 0, sw);
    int *arr2 = TestSortHelper::copyIntArray(arr1, n);
    int *arr3 = TestSortHelper::copyIntArray(arr1, n);


    TestSortHelper::testSort("merge up-bottom Sort Sort", mergeSortUB, arr1, n);
    TestSortHelper::testSort("quick Sort 2_stack_err", quickSort2_stack_err, arr2, n);
    TestSortHelper::testSort("quick Sort 2 ", quickSort2, arr3, n);

    cout<<"swaptimes_p2: "<<swaptimes_p2<<endl;
    cout<<"swaptimes_p2_stack_err: "<<swaptimes_p2_stack_err<<endl;

    delete[] arr1;
    delete[] arr2;


}
int main2(){
    int n = 1000000;
    cout << "Test for Random Array, size = " << n << ", randome range [0, " << n << "]" << endl;
    int *arr1 = TestSortHelper::generateRandomArray(n, 0, n);
    int *arr2 = TestSortHelper::copyIntArray(arr1, n);
    int *arr3 = TestSortHelper::copyIntArray(arr1, n);
    int *arr4 = TestSortHelper::copyIntArray(arr1, n);


    TestSortHelper::testSort("merge up-bottom Sort Sort", mergeSortUB, arr1, n);
    TestSortHelper::testSort("quick Sort 1 with random invot", quickSort1, arr2, n);
    TestSortHelper::testSort("quick Sort 2 double sort", quickSort2, arr3, n);
    TestSortHelper::testSort("quick Sort 3 ways sort", quickSort3, arr4, n);

    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;


    int swaptimes = 10;
    cout << "Test for Nearly Ordered Array, size = " << n << ", randome range [0, " << n << "]" << endl;
    arr1 = TestSortHelper::generateNearlyOrderedArray(n, swaptimes);
    arr2 = TestSortHelper::copyIntArray(arr1, n);
    arr3 = TestSortHelper::copyIntArray(arr1, n);
    arr4 = TestSortHelper::copyIntArray(arr1, n);

    TestSortHelper::testSort("merge up-bottom Sort Sort", mergeSortUB, arr1, n);
    TestSortHelper::testSort("quick Sort 1 with random invot", quickSort1, arr2, n);
    TestSortHelper::testSort("quick Sort 2 double sort", quickSort2, arr3, n);
    TestSortHelper::testSort("quick Sort 3 ways sort", quickSort3, arr4, n);

    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;

    int range = 10;
    cout << "Test for Nearly Ordered Array, size = " << n << ", randome range [0, " << range << "]" << endl;
    arr1 = TestSortHelper::generateNearlyOrderedArray(n, swaptimes);
    arr2 = TestSortHelper::copyIntArray(arr1, n);
    arr3 = TestSortHelper::copyIntArray(arr1, n);
    arr4 = TestSortHelper::copyIntArray(arr1, n);

    TestSortHelper::testSort("merge up-bottom Sort Sort", mergeSortUB, arr1, n);
    TestSortHelper::testSort("quick Sort 1 with random invot", quickSort1, arr2, n);
    TestSortHelper::testSort("quick Sort 2 double sort", quickSort2, arr3, n);
    TestSortHelper::testSort("quick Sort 3 ways sort", quickSort3, arr4, n);

    delete[] arr1;
    delete[] arr2;
    delete[] arr3;
    delete[] arr4;
}